package dramsy_christian_bellamn_floyd;

import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Classe Representant un graphe
 *
 * @author <a href="mailto:christian.dramsy@gmail.com">DRAMSY Christian</a>
 */
public class Graphe {

    /**
     * La matrice d'adjacence du graphe.
     */
    private int[][] matriceAdj;
    /**
     * Determine si le graphe est orienté ou pas
     */
    private boolean oriented;

    /**
     * Retourne une matrice d'adjacence d'un graphe orienté à partir d'un fichier texte
     * @param filename Le fichier où est stocké le graphe
     * @return La matrice d'adjascence
     * @throws IOException
     */
    private int[][] buildMatriceAdjacence(String filename) throws IOException {
        int j;  //  premier sommet
        int k;  //  deuxieme sommet
        int c;  //  cout entre le sommet j et k
        int nodeNumber;
        int[][] matrice;
        BufferedReader input = new BufferedReader(new FileReader(filename));
        String line1 = input.readLine();
        nodeNumber = Integer.parseInt(line1);
        matrice = new int[nodeNumber][nodeNumber];

        while (true) {
            String line = input.readLine();
            if (line == null) {
                break;
            }
            StringTokenizer tok = new StringTokenizer(line, " ");
            j = Integer.parseInt(tok.nextToken());
            j--;    //  Decrementaion car l'index commen à zero

            //  verification s'il y a encore des token
            if (tok.hasMoreTokens()) {
                c = 1;
                k = Integer.parseInt(tok.nextToken());
                k--;    //  Decrementaion car l'index commen à zero
                //  verification s'il y a encore un token pour le cout du graphe
                if (tok.hasMoreTokens()) {
                    c = Integer.parseInt(tok.nextToken());
                }
                matrice[j][k] = c;
                //  Si le graphe n'exst pas orienté on fait aussi dans le sens inverses
                if (!this.oriented) {
                    matrice[k][j] = c;
                }
            }
        }   // while

        return matrice;
    }

    /**
     * Constructeur de la classe Graphe
     * @param filename
     * @param isOriented Determine si le graphe est un graphe orienté ou pas
     */
    public Graphe(String filename, boolean isOriented) {
        this.oriented = isOriented;
        try {
            this.matriceAdj = this.buildMatriceAdjacence(filename);
        } catch (IOException ex) {
            Logger.getLogger(Graphe.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    /**
     * Verifie si le graphe contient un circuit à partir d'un sommet
     * @param beginNode Le sommet à verifier
     * @return
     */
    public boolean containsCircuit(int beginNode) {
        LinkedList<Integer> pile = new LinkedList<Integer>();

        int[] nbPassage = new int[this.matriceAdj.length];
        boolean[] successeur;
        for (int i = 0; i < this.matriceAdj.length; i++) {
            nbPassage[i] = 0;
        } // for

        //  Insertion du premier sommet
        pile.addFirst(beginNode);

        while (!pile.isEmpty()) {
            int s = pile.removeFirst();
            successeur = this.successeurs(s);
            for (int i = 0; i < successeur.length; i++) {
                //  si c'est vraiment un voisin
                if (successeur[i] == true) {
                    //  On est deja apassé ici
                    if (nbPassage[i] > 0) {
                        if (beginNode == i) {
                            return true;
                        }
                    } else {
                        nbPassage[s]++;
                        pile.addFirst(i);
                    }
                } // if
            } // for

        } // while

        return false;
    }

    /**
     * Verifie si le graphe contien un circuit
     * @return
     */
    public boolean containsCircuit() {
        for (int i = 0; i < this.matriceAdj.length; i++) {
            if (this.containsCircuit(i)) {
                return true;
            }
        }
        return false;
    }

    public int[][] getMatriceAdj() {
        return matriceAdj;
    }
    
    /**
     * Retourne l'ordre du graphe
     * @return 
     */
    public int getOrdre() {
        return this.matriceAdj.length;
    }
    
    public void setMatriceAdj(int[][] matriceAdj) {
        this.matriceAdj = matriceAdj;
    }

    /**
     * Retourne la valeur matriceAdj[ligne][colonne]
     * @param ligne
     * @param colonne
     * @return
     */
    public int getMatriceAdjValue(int ligne, int colonne) {
        return this.matriceAdj[ligne][colonne];
    }

    public boolean isOriented() {
        return oriented;
    }
    
    /**
     * Retourne les predecesseurs d'un node dans un graphe.
     * @param node
     * @param matrice
     * @return
     */
    public boolean[] predecesseurs(int node) {
        boolean[] v = new boolean[this.matriceAdj.length];
        for (int i = 0; i < this.matriceAdj.length; i++) {
            v[i] = false;
        }
        for (int i = 0; i < this.matriceAdj.length; i++) {
            if (this.matriceAdj[i][node] > 0) {
                v[i] = true;
            }
        }
        return v;
    }

    /**
     * Verifie si node2 est predecesseur de node1
     * @param node1
     * @param node2
     * @return
     */
    public boolean isPredecesseur(int node1, int node2) {
        //  tout les predecesseurs de node1
        boolean pred[] = this.predecesseurs(node1);
        return (pred[node2]);
    }

    /**
     * Retourne les successeurs d'un sommet
     * @param node LE sommet
     * @return
     */
    public boolean[] successeurs(int node) {
        boolean[] v = new boolean[this.matriceAdj.length];
        for (int i = 0; i < this.matriceAdj.length; i++) {
            v[i] = false;
        }
        for (int i = 0; i < this.matriceAdj.length; i++) {
            if (this.matriceAdj[node][i] > 0) {
                v[i] = true;
            }
        }
        return v;
    }
}
